<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Background: Constraint Satisfaction Problems
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial099.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial098.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial101.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc198">14.2</A>&nbsp;&nbsp;Background: Constraint Satisfaction Problems</H2>
<A NAME="@default355"></A>
<A NAME="@default356"></A>
<A NAME="csp"></A>

There is a large body of scientific work and literature about
Constraint Satisfaction Problems, or CSPs.
CSPs are a restricted class of constraint problems with the
following properties
<UL CLASS="itemize"><LI CLASS="li-itemize">
there is a fixed set of variables <I>X</I><SUB>1</SUB>, ..., <I>X</I><SUB><I>n</I></SUB>
<LI CLASS="li-itemize">every variable <I>X</I><SUB><I>i</I></SUB> has a finite domain <I>D</I><SUB><I>i</I></SUB> of values that the variable
 is allowed to take. In general, this can be an arbitrary, unordered
 domain.
<LI CLASS="li-itemize">usually one considers only binary (2-variable) constraints <I>c</I><SUB><I>ij</I></SUB>(<I>X</I><SUB><I>i</I></SUB>,<I>X</I><SUB><I>j</I></SUB>).
 Every constraint is simply defined as a set of pairs of consistent values.
<LI CLASS="li-itemize">the problem is to find a valuation (labeling) of the variables such
 that all the constraints are satisfied.
</UL>
The restriction to binary constraints is not really limiting since every CSP
can be transformed into a binary CSP. However, this is often not necessary
since many algorithms can be generalised to n-ary constraints.<BR>
<BR>
A CSP network is the graph formed by considering the variables as nodes
and the constraints as arcs between them.
In such a network, several levels of consistency can be defined:
<A NAME="@default357"></A>
<A NAME="@default358"></A>
<A NAME="@default359"></A>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>Node consistency</B><DD CLASS="dd-description"> &forall;<I>v</I> &isin; <I>D</I><SUB><I>i</I></SUB> : <I>c</I><SUB><I>i</I></SUB>(<I>v</I>)
 (not very interesting). It means that
	all unary constraints are reflected in the domains
<DT CLASS="dt-description"><B>Arc consistency</B><DD CLASS="dd-description"> &forall;<I>v</I> &isin; <I>D</I><SUB><I>i</I></SUB> &exist;<I>w</I> &isin; <I>D</I><SUB><I>j</I></SUB> : <I>c</I><SUB><I>ij</I></SUB>(<I>v</I>,<I>w</I>)
	(most practically relevant).
	It means that for every value in the domain of one
	variable, there is a compatible value in the domain of the
	other variable in the constraint. In practice, constraints
	are symmetric, so the reverse property also holds.
<DT CLASS="dt-description"><B>Path consistency</B><DD CLASS="dd-description"> &forall;<I>v</I> &isin; <I>D</I><SUB><I>i</I></SUB> &forall;<I>w</I> &isin; <I>D</I><SUB><I>j</I></SUB> &exist;<I>u</I> &isin; <I>D</I><SUB><I>k</I></SUB> : <I>c</I><SUB><I>ik</I></SUB>(<I>v</I>,<I>u</I>), <I>c</I><SUB><I>kj</I></SUB>(<I>u</I>,<I>w</I>)
 (usually too expensive). One can show that this property extends to
	whole paths, i.e. on any path of constraints between variables i and j 
	the variables have domain values which are compatible with any
	domain values for i and j.
</DL>
Note that neither of these conditions is sufficient for the
problem to be satisfiable. It is still necessary to search for solutions.
Computing networks with these consistency levels can however be a useful
intermediate step to finding a solution to the CSP.<BR>
<BR>
Consequently, a complete CSP solver needs the following design decisions:
<UL CLASS="itemize"><LI CLASS="li-itemize">
what level of consistency do we want to employ?
<LI CLASS="li-itemize">at what time during search do we want to (re)establish this consistency?
<LI CLASS="li-itemize">what algorithm do we use to establish this consistency?
</UL>
In practice, the most relevant consistency level is arc-consistency.
Consequently, a number of algorithms have been proposed for the
purpose of establishing arc-consistency. The algorithms used in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>
<A NAME="@default360"></A>
are mostly variants of AC-3 [<A HREF="tutorial133.html#mackworth77"><CITE>16</CITE></A>]
<A NAME="@default361"></A>
and AC-5 [<A HREF="tutorial133.html#vanhentenryck92generic"><CITE>10</CITE></A>].<BR>
<BR>
<HR>
<A HREF="tutorial099.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial098.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial101.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
